package top.humbleyuan.double_pointer;

import top.humbleyuan.datastructure.linkedlist.LinkNode;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:57
 * @Des 删除链表倒数第n个节点
 */
public class LeetCode_19 {
    public static void main(String[] args) {
        // 普通解法
        //m1();

        // 快慢指针
        m2();
    }

    public static void m1() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2,3};
        head = LinkNode.formLink(head,vals);
        int n = 3;


        LinkNode f = head;
        int i ;
        for(i = 0;f != null;i++) {
            f = f.next;
        }
        if( i == n) {
            head = head.next;
            LinkNode.headToString(head);
            return;
        }

        f = head;
        //把i-n连到i-n+2上
        for(int j = 1;j < i - n;j++) {
            f = f.next;
        }
        f.next = f.next.next;

        LinkNode.headToString(head);
    }

    public static void m2() {
        /**
         * 一次遍历，快慢指针
         * 使两个指针始终间隔n个距离，那么快指针到底时，满指针正好到倒数第n
         */
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(1);
        int[] vals = {2};
        head = LinkNode.formLink(head,vals);
        int n = 2;

        LinkNode dummyHead = new LinkNode(0);
        dummyHead.next = head;
        LinkNode fast = dummyHead;
        LinkNode slow = dummyHead;

        int i;
        for(i = 0;fast.next != null; i++) {
            fast = fast.next;
            if(i >= n){
                slow = slow.next;
            }
        }

        /**
         * slow的next就是倒数第k个节点
         */
        slow.next = slow.next.next;

        LinkNode.headToString(dummyHead.next);
    }
}
